/*

Archivo: "hastable.h"

Implementación de una tabla de hash que utiliza la función de
hashing murmur.

Autor: Diego Luna

Primera versión: 5-6-2012

*/


#ifndef __HASHTABLE_H_INCLUDED
#define __HASHTABLE_H_INCLUDED


#include <iostream>
#include <cstdlib>
#include <typeinfo>
#include <cmath>
#include <vector>

// Solo se compila en modo de pruebas.
#if (CONTAINER_DEBUG == 1)
#include <algorithm>
#endif

#include "globals.h"
#include "bases.h"



#define MIN_LOAD_FACTOR 0.5
#define MAX_LOAD_FACTOR 0.85
#define DEFAULT_LOAD_FACTOR 0.70

#define DEFAULT_TABLE_SIZE 10
#define TABLE_GROW_SCALE 2

#define SEED 7504

/* ========================= Hash_Table_Murmur - Begin ========================== */

template <typename T>
class Hash_Table_Murmur: public Base_Container<T>
{

public:

    // Iterador bidireccional para la tabla de hash.
    typedef Base_Iterator<T, DEFAULT_ITERATOR> Hash_Table_Iterator;

    // Typedef del Nodo interno de las listas.
    typedef typename Double_Linked_List<T>::List_Node Hash_Table_Node;

    // Typedef para simplificar la sintáxis.
    typedef std::vector<Double_Linked_List<T>* > Internal_Table;

    // ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

    // Constructor.
    Hash_Table_Murmur(double = DEFAULT_LOAD_FACTOR);

    // Constructor copia.
    Hash_Table_Murmur(const Hash_Table_Murmur&);

    // Destructor.
    virtual ~Hash_Table_Murmur();

    // ++++++++++++++++++++++++ Constructores\Destructores - End +++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Métodos públicos - Begin +++++++++++++++++++++++++++++++++++++++

    // Calcula el factor de carga de la tabla de hash.
    double load_factor(bool future_value = false);

    // ++++++++++++++++++++++++ Métodos públicos - End +++++++++++++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Operadores - Begin ++++++++++++++++++++++++++++++++++++++++++++++

    // Operador de asignación.
    Hash_Table_Murmur<T>& operator=(const Hash_Table_Murmur&);

    // Operador de asignación (se sobreescribe para la asignación cuando se hace por
    // desreferencia de punteros a la clase base).
    virtual SetImplementation<T>& operator=(const SetImplementation<T>&);

    // ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++++++++

protected:

    // ++++++++++++++++++++++++ Métodos protegidos - Begin ++++++++++++++++++++++++++++++++++++++

    // Métodos sobrescritos - Begin -------------------------------------------------------------

    // Devuelve un puntero al nodo con la clave indicada, devuelve NULL en caso de no encontrarse.
    virtual Base_Node<T>* find_node(const T&) const;

    // Agrega un elemento al contenedor devolviendo un puntero al nodo insertado o NULL si no se insertó.
    virtual Base_Node<T>* add_node(const T&, bool);

    // Elimina un elemento del contenedor.
    // Este método es llamado primero, en
    // caso de devolver "false" se llama al
    // que toma un nodo por parámetro.
    virtual bool delete_node_by_key(const T&, bool&);

    // Elimina un nodo del contenedor.
    virtual void delete_node(Base_Node<T>*);

    // Elimina todos los elementos del contenedor.
    virtual void delete_nodes();

    // Devuelve el sucesor de un nodo.
    virtual Base_Node<T>* next(Base_Node<T>*, Iterator_Type) const;

    // Devuelve el predecesor de un nodo.
    virtual Base_Node<T>* previous(Base_Node<T>*, Iterator_Type) const;

    // Devuelve el primer nodo para un tipo de iterador.
    virtual Base_Node<T>* first(Iterator_Type) const;

    // Devuelve el último nodo para un tipo de iterador.
    virtual Base_Node<T>* last(Iterator_Type) const;

    // Métodos sobrescritos - End ---------------------------------------------------------------

    // ++++++++++++++++++++++++ Métodos protegidos - End ++++++++++++++++++++++++++++++++++++++++

private:

    //************************
    // Atributos de Hash_Table_Murmur.

    // Tabla.
    Internal_Table* table_;

    // Factor de ocupación deseado.
    double desired_load_factor_;
    //************************


    // ++++++++++++++++++++++++ Métodos privados - Begin ++++++++++++++++++++++++++++++++++++++++

    // Devuelve el nodo siguiente al dado.
    Hash_Table_Node* succesor_hash_table_node(Hash_Table_Node*) const;

    // Devuelve el nodo anterior al dado.
    Hash_Table_Node* predecessor_hash_table_node(Hash_Table_Node*) const;

    // Inserta un nodo en la tabla de hash con la clave dada.
    Hash_Table_Node* insert_hash_table_node(const T&, bool);

    // Elimina un nodo de la tabla de hash.
    bool delete_hash_table_node_by_key(const T&);

    // Encontrar nodo con clave dada, devolviendo el puntero corespondiente.
    Hash_Table_Node* find_hash_table_node(const T&) const;

    // Elimina todos los nodos de una tabla.
    void clear_hash_table_nodes(Internal_Table*);

    // "Hashea" el dato indicado y devuelve la posición obtenida.
    size_t calculate_table_position(const T&) const;

    // Recrea la tabla para mantener el factor de
    // carga por debajo del valor máximo fijado.
    void recreate_hash_table();

    // ++++++++++++++++++++++++ Métodos privados - End ++++++++++++++++++++++++++++++++++++++++++

};

/* ========================= Hash_Table_Murmur - End ============================ */


// ++++++++++++++++++++++++ Static Functions - Begin +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

// Versión de la función de hash murmur que es "endian neutral" y "align neutral", es más
// lenta que la versión menos portable, pero más segura en más plataformas.
// Tiene igualmente el requerimiento de "sizeof(int) == 4".
static unsigned int MurmurHashNeutral2 (const void * key, int len, unsigned int seed = SEED)
{
    const unsigned int m = 0x5bd1e995;
    const int r = 24;

    unsigned int h = seed ^ len;

    const unsigned char * data = (const unsigned char *)key;

    while(len >= 4)
    {
        unsigned int k;

        k  = data[0];
        k |= data[1] << 8;
        k |= data[2] << 16;
        k |= data[3] << 24;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    switch(len)
    {
    case 3:
        h ^= data[2] << 16;
    case 2:
        h ^= data[1] << 8;
    case 1:
        h ^= data[0];
        h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

// ++++++++++++++++++++++++ Static Functions - End +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Constructores\Destructores [Hash_Table_Murmur] - Begin +++++++++++++++++++++++++++++

// Constructor.
template <typename T>
Hash_Table_Murmur<T>::Hash_Table_Murmur(double desired_load_factor):
    table_(NULL), desired_load_factor_(DEFAULT_LOAD_FACTOR)
{
    if (desired_load_factor < MIN_LOAD_FACTOR)
        desired_load_factor_ = MIN_LOAD_FACTOR;
    else if (desired_load_factor > MAX_LOAD_FACTOR)
        desired_load_factor_ = MAX_LOAD_FACTOR;

    // Creo la tabla.
    table_ = new Internal_Table;

    table_->resize(DEFAULT_TABLE_SIZE);
}

// Constructor copia.
template <typename T>
Hash_Table_Murmur<T>::Hash_Table_Murmur(const Hash_Table_Murmur& hashtable):
    table_(NULL), desired_load_factor_(hashtable.desired_load_factor_)
{
    // Llamo al operador de asignación.
    *this = hashtable;
}

// Destructor.
template <typename T>
Hash_Table_Murmur<T>::~Hash_Table_Murmur()
{
    // Libero toda la memoria utilizada por los nodos.
    Base_Container<T>::wipe();

    // Libero la tabla.
    if (table_ != NULL)
        delete table_;
}

// ++++++++++++++++++++++++ Constructores\Destructores [Hash_Table_Murmur] - End +++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos públicos [Hash_Table_Murmur] - Begin +++++++++++++++++++++++++++++++++++++++

// Calcula el factor de carga de la tabla de hash.
template <typename T>
double Hash_Table_Murmur<T>::load_factor(bool future_value)
{
    size_t realsize = Base_Container<T>::size();

    if (future_value)
        realsize++;

    return (double(realsize)/double(table_->size()));
}

// ++++++++++++++++++++++++ Métodos públicos [Hash_Table_Murmur] - End +++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Hash_Table_Murmur] - Begin ++++++++++++++++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
Hash_Table_Murmur<T>& Hash_Table_Murmur<T>::operator=(const Hash_Table_Murmur& ht)
{
    // Verifico la autoasignación.
    if (&ht == this)
        return *this;

    // Llamo al operador de asignación de la clase base.
    Base_Container<T>::operator=(ht);

	// Redimensiono el vector al tamaño del original.
	table_->resize(ht.table_->size());

	// Copio cada una de las listas (buckets).
    for (size_t i = 0; i < ht.table_->size(); i++)
    {
        Double_Linked_List<T>* list = (*ht.table_)[i];

		// Si existe la lista la copio.
        if (list != NULL)
			(*table_)[i] = new Double_Linked_List<T>(*list);
		else
			(*table_)[i] = NULL;
    }

    return *this;
}

// Operador de asignación (se sobreescribe para la asignación cuando se hace por
// desreferencia de punteros a la clase base).
template <typename T>
SetImplementation<T>& Hash_Table_Murmur<T>::operator=(const SetImplementation<T>& setimpl)
{
    if (typeid(setimpl) != typeid(*this))
        return SetImplementation<T>::operator=(setimpl);
    else
        return operator=(static_cast<const Hash_Table_Murmur<T>& >(setimpl));
}

// ++++++++++++++++++++++++ Operadores [Hash_Table_Murmur] - End ++++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos protegidos - Begin ++++++++++++++++++++++++++++++++++++++

// Métodos sobrescritos - Begin -------------------------------------------------------------

// Devuelve un puntero al nodo con la clave indicada, devuelve NULL en caso de no encontrarse.
template <typename T>
Base_Node<T>* Hash_Table_Murmur<T>::find_node(const T& key) const
{
    return find_hash_table_node(key);
}

// Agrega un elemento al contenedor devolviendo un puntero al nodo insertado o NULL si no se insertó.
template <typename T>
Base_Node<T>* Hash_Table_Murmur<T>::add_node(const T& key, bool accept_repeated)
{
    double factor = load_factor(true);

    // Si el agregar un nodo hace superar el factor de
    // carga máximo fijado, recreo la tabla de hash.
    if (factor > desired_load_factor_)
        recreate_hash_table();

    return insert_hash_table_node(key, accept_repeated);
}

// Elimina un elemento del contenedor.
// Este método es llamado primero, en
// caso de devolver "false" se llama al
// que toma un nodo por parámetro.
template <typename T>
bool Hash_Table_Murmur<T>::delete_node_by_key(const T& key, bool& deleted)
{
    deleted = delete_hash_table_node_by_key(key);

    return true;
}

// Elimina un nodo del contenedor.
template <typename T>
void Hash_Table_Murmur<T>::delete_node(Base_Node<T>*)
{
    // En este contenedor no se elimina por nodo.
}

// Elimina todos los elementos del contenedor.
template <typename T>
void Hash_Table_Murmur<T>::delete_nodes()
{
    // Libero toda la memoria utilizada.
    clear_hash_table_nodes(table_);
}

// Devuelve el sucesor de un nodo.
template <typename T>
Base_Node<T>* Hash_Table_Murmur<T>::next(Base_Node<T>* n, Iterator_Type) const
{
    Hash_Table_Node* node = static_cast<Hash_Table_Node*>(n);

    return succesor_hash_table_node(node);
}

// Devuelve el predecesor de un nodo.
template <typename T>
Base_Node<T>* Hash_Table_Murmur<T>::previous(Base_Node<T>* n, Iterator_Type) const
{
    Hash_Table_Node* node = static_cast<Hash_Table_Node*>(n);

    return predecessor_hash_table_node(node);
}

// Devuelve el primer nodo para un tipo de iterador.
template <typename T>
Base_Node<T>* Hash_Table_Murmur<T>::first(Iterator_Type itt) const
{
    Double_Linked_List<T>* list;

    // Encuentro la primer lista no vacía en la tabla y
    // devuelvo su primer nodo.
    for (size_t i = 0; i < table_->size(); i++)
    {
        list = (*table_)[i];

        if ((list != NULL) && (!(list->is_empty())))
            return list->first(itt);
    }

    return NULL;
}

// Devuelve el último nodo para un tipo de iterador.
template <typename T>
Base_Node<T>* Hash_Table_Murmur<T>::last(Iterator_Type itt) const
{
    Double_Linked_List<T>* list;

    // Encuentro la última lista no vacía en la tabla y
    // devuelvo su último nodo.
    for (long int i = (table_->size() - 1); i >= 0; i--)
    {
        list = (*table_)[i];

        if ((list != NULL) && (!list->is_empty()))
            return list->last(itt);
    }

    return NULL;
}

// Métodos sobrescritos - End ---------------------------------------------------------------

// ++++++++++++++++++++++++ Métodos protegidos - End ++++++++++++++++++++++++++++++++++++++++

// ++++++++++++++++++++++++ Métodos privados [Hash_Table_Murmur] - Begin ++++++++++++++++++++++++++++++++++++++++

// Devuelve el nodo siguiente al dado.
template <typename T>
typename Hash_Table_Murmur<T>::Hash_Table_Node* Hash_Table_Murmur<T>::succesor_hash_table_node(
    Hash_Table_Node* htn) const
{
    // Devuelvo nulo si el original es nulo.
    if (htn == NULL)
        return NULL;

    bool list_found = false;

    // Encuentro en la tabla la lista a la que pertenece el nodo,
    // y devuelvo su sucesor en esta lista o de ser el último,
    // devuelvo el primer nodo de la próxima lista no vacía,
    // si no hay el nodo era el último y no tiene sucesor.
    for (size_t i = 0; i < table_->size(); i++)
    {
        Double_Linked_List<T>* list = (*table_)[i];

        if (!list_found && (list == &htn->container()))
        {
            list_found = true;

            Hash_Table_Node* node = list->succesor_list_node(htn);

            if (node != NULL)
                return node;
        }
        else if ((list_found) && (list != NULL) && (list->size() > 0))
        {
            return list->first_list_node();
        }
    }

    return NULL;
}

// Devuelve el nodo anterior al dado.
template <typename T>
typename Hash_Table_Murmur<T>::Hash_Table_Node* Hash_Table_Murmur<T>::predecessor_hash_table_node(
    Hash_Table_Node* htn) const
{
    // Devuelvo nulo si el original es nulo.
    if (htn == NULL)
        return NULL;

    Double_Linked_List<T>* list;

    Hash_Table_Node* node;

    bool list_found = false;

    // Encuentro en la tabla la lista a la que pertenece el nodo,
    // y devuelvo su predecesor en esta lista o de ser el primero,
    // devuelvo el último nodo de la anterior lista no vacía,
    // si no hay el nodo era el primero y no tiene predecesor.
    for (long int i = (table_->size() - 1); i >= 0; i--)
    {
        list = (*table_)[i];

        if (!list_found && (list == &htn->container()))
        {
            list_found = true;

            node = list->predecessor_list_node(htn);

            if (node != NULL)
                return node;
        }
        else if ((list_found) && (list != NULL) && (list->size() > 0))
        {
            return list->last_list_node();
        }
    }

    return NULL;
}

// Inserta un nodo en la lista con la clave dada.
template <typename T>
typename Hash_Table_Murmur<T>::Hash_Table_Node* Hash_Table_Murmur<T>::insert_hash_table_node(
    const T& key, bool accept_repeated)
{
    size_t position = calculate_table_position(key);

    Double_Linked_List<T>* list = (*table_)[position];

    if (list == NULL)
        list = ((*table_)[position] = new Double_Linked_List<T>);

    return static_cast<Hash_Table_Node*>(list->add_hidden(key, accept_repeated));
}

// Elimina un nodo de la lista.
template <typename T>
bool Hash_Table_Murmur<T>::delete_hash_table_node_by_key(const T& key)
{
    Double_Linked_List<T>* list = (*table_)[calculate_table_position(key)];

    // Busco en la lista que está en la posición indicada, si no hay lista
    // definida en la posición indicada no hay nada que borrar, sino
    // borro el nodo indicado de la lista.
    if (list != NULL)
        return list->remove(key);
    else
        return false;
}

// Encontrar nodo con clave dada, devolviendo el puntero corespondiente.
template <typename T>
typename Hash_Table_Murmur<T>::Hash_Table_Node* Hash_Table_Murmur<T>::find_hash_table_node(
    const T& key) const
{
    const Double_Linked_List<T>* list = (*table_)[calculate_table_position(key)];

    // Busco en la lista que está en la posición indicada, si no hay lista
    // definida en la posición indicada devuelvo NULL.
    if (list == NULL)
        return NULL;
    else
        return list->find_list_node(key);
}

// Elimina todos los nodos.
template <typename T>
void Hash_Table_Murmur<T>::clear_hash_table_nodes(Internal_Table* table)
{
    if (table == NULL)
        return;

    for (size_t i = 0; i < table->size(); i++)
    {
        if ((*table)[i] != NULL)
        {
            delete (*table)[i];
            (*table)[i] = NULL;
        }
    }
}

// "Hashea" el dato indicado y devuelve la posición obtenida.
template <typename T>
size_t Hash_Table_Murmur<T>::calculate_table_position(const T& key) const
{
    const void* pkey = NULL;
    size_t key_len = 0;

    if (typeid(T) == typeid(int))
    {
        pkey = &key;
        key_len = sizeof(int);
    }
    else if (typeid(T) == typeid(float))
    {
        pkey = &key;
        key_len = sizeof(int);
    }
    else if (typeid(T) == typeid(std::string))
    {
        // Esto es horrible, pero no encuentro otra manera
        // de que todos los compiladores acepten a key como
        // string para poder tomar el puntero al array
        // estilo "C", la única manera elegante parece ser usando
        // ténicas que solo se sorportan en "C++0x"\"C++11".
        // El poder hacer compilación condicional basada en
        // parámetros de template haría esto mucho más elegante.

        const void* dummy = &key;

        pkey = static_cast<const std::string*>(dummy)->c_str();
        key_len = static_cast<const std::string*>(dummy)->length();

    }
    else
        FATAL_ERROR(BAD_HASH_TYPE);

    // Calculo el hash en base a la clave en forma "raw".
    return (MurmurHashNeutral2(pkey, key_len) % table_->size());
}

// Recrea la tabla para mantener el factor de
// carga por debajo del valor máximo fijado.
template <typename T>
void Hash_Table_Murmur<T>::recreate_hash_table()
{
    // Creo la nueva tabla.
    Internal_Table* new_table = new Internal_Table;

    // Dimensiono el tamaño de la nueva tabla.
    new_table->resize((table_->size())*TABLE_GROW_SCALE);

    // Retengo la vieja tabla.
    Internal_Table* old_table = table_;

    // Temporariamente desconecto la tabla del contenedor.
    table_ = NULL;

    // Reinicializo el contenedor (el contador de elementos).
    Base_Container<T>::wipe();

    // Asigno la nueva tabla
    table_ = new_table;

    // Ingreso todos los elementos de la vieja tabla
    // en el contenedor usando iteradores y el método "add".
    for (size_t i = 0; i < old_table->size(); i++)
    {
        Double_Linked_List<T>* list;

        if ((list = (*old_table)[i]) != NULL)
        {
            for (typename Double_Linked_List<T>::DL_List_Iterator it = list->begin();
                    it != list->end(); it++)
                Base_Container<T>::add(*it, true);
        }
    }

    // Elimino los nodos de la vieja tabla.
    clear_hash_table_nodes(old_table);

    // elimino la vieja tabla.
    delete old_table;
}

// ++++++++++++++++++++++++ Métodos privados [Hash_Table_Murmur] - End ++++++++++++++++++++++++++++++++++++++++++


#endif
